#include<iostream>
#include<vector>
using namespace std;

class Solution {
    // int minSum;
    int arr[210][210];
    int dfs(int level, int posj, vector<vector<int>>& triangle) {
        if (level == triangle.size() - 1) {
            return triangle[level][posj];
        }
        if (arr[level][posj] != INT_MAX)
            return arr[level][posj];

        int left = dfs(level + 1, posj, triangle);
        int right = dfs(level + 1, posj + 1, triangle);
        arr[level][posj] = triangle[level][posj] + min(left, right);
        return arr[level][posj];
    }

public:
    int minimumTotal(vector<vector<int>>& triangle) {
        // minSum = INT_MAX;
        for (int i = 0; i < 204; i++) {
            for (int j = 0; j < 204; j++) {
                arr[i][j] = INT_MAX;
            }
        }
        return dfs(0, 0, triangle);
    }
};

class Solution2 {
    int minSum;

    void dfs(int level, int posj, int curSum, vector<vector<int>>& triangle)
    {
        if (level == triangle.size()) {
            minSum = min(curSum, minSum);
            return;
        }
        dfs(level + 1, posj, curSum + triangle[level][posj], triangle);
        dfs(level + 1, posj + 1, curSum + triangle[level][posj + 1], triangle);
    }
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        minSum = INT_MAX;
        dfs(1, 0, triangle[0][0], triangle);
        return minSum;
    }
};